Codeforces Round #562 (Div. 2) B - Pairs
B. Pairs
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Toad Ivan has m
pairs of integers, each integer is between 1 and n, inclusive. The pairs are (a1,b1),(a2,b2),…,(am,bm)
.
He asks you to check if there exist two integers x
and y (1≤x<y≤n) such that in each given pair at least one integer is equal to x or y
.
Input
The first line contains two space-separated integers n
and m (2≤n≤300000, 1≤m≤300000
) — the upper bound on the values of integers in the pairs, and the number of given pairs.
The next m
lines contain two integers each, the i-th of them contains two space-separated integers ai and bi (1≤ai,bi≤n,ai≠bi) — the integers in the i
-th pair.
Output
Output "YES" if there exist two integers x
and y (1≤x<y≤n) such that in each given pair at least one integer is equal to x or y
. Otherwise, print "NO". You can print each letter in any case (upper or lower).
Examples
Input
Copy
4 6 1 2 1 3 1 4 2 3 2 4 3 4
Output
Copy
NO
Input
Copy
5 4 1 2 2 3 3 4 4 5
Output
Copy
YES
Input
Copy
300000 5 1 2 1 2 1 2 1 2 1 2
Output
Copy
YES
Note
In the first example, you can't choose any x
, y
because for each such pair you can find a given pair where both numbers are different from chosen integers.
In the second example, you can choose x=2
and y=4
.
In the third example, you can choose x=1
and y=2
.
思路：我的思路是把每个数的所有位置分别存到1个set里去，然后判断有没有两个数去掉重复（用set.find）位置后位置数和等于n。。。这个思路写了我快一个小时，实际上以第一个数对中的x，y为基准，把其他数对中含有x的去掉，剩下的数对如果都含有y，那就输出YES，否则输出NO就好了
By jswwsj, contest: Codeforces Round #562 (Div. 2), problem: (B) Pairs, Accepted, #
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<set>
#define ll long long
#define mod 1000000007
using namespace std;
typedef struct Dt
{
set<int>q;
}Dt;
Dt a[300050],b[305000];
bool cmp(Dt x,Dt y)
{
return x.q.size()>y.q.size();
}
int main()
{
int n,m;
while(scanf("%d %d",&n,&m)!=EOF)
{
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
a[x].q.insert(i);
a[y].q.insert(i);
}
int t=0;
for(int i=1;i<=n;i++)
{
if(!a[i].q.empty())
{
a[i].q.swap(b[t].q);
//printf("i=%d b.[%d].size=%d\n",i,t,b[t].q.size());
t++;
}
}
sort(b,b+t,cmp);
int flag=0;
for(int i=0;i<t;i++)
{
if(b[i].q.size()+b[i+1].q.size()<m) break;
for(int j=i+1;j<t;j++)
{
Dt x;
int sum=b[i].q.size()+b[j].q.size();
while(!b[j].q.empty())
{
int m;
m=*b[j].q.begin();
b[j].q.erase(m);
x.q.insert(m);
if(b[i].q.find(m)!=b[i].q.end()) sum--;
}
b[j].q.swap(x.q);
//printf("b[%d].size=%d b[%d].size=%d sum=%d\n",i,b[i].q.size(),j,b[j].q.size(),sum);
if(sum>=m)
{
flag=1;
break;
}
}
if(flag==1) break;
}
if(flag==1) printf("YES\n");
else printf("NO\n");
}
}
