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

4 6 1 2 1 3 1 4 2 3 2 4 3 4

output

NO

題目大意：給m對數，每個數字都在1~n的范圍內，求解是否存在一對數，使得每組輸入的數據中至少有一個在這對數中，如果存在，輸出YES，否則輸出NO。

思路：
既然每組數至少有一個存在與正確答案中，如果最終結果是YES，那么在第一對數里面至少有一個數字在正確答案中。可以遍歷第一對數的兩個數字，然后枚舉給定的m組數，如果某一組數的兩個值都沒有出現，讓這兩個數的標記位++，記錄不滿足條件的個數的變量 sum 也 ++。
如果一共有 t 組不滿足條件，恰好有一個數字不滿足條件的次數為 t ，也就是說可以用 t 和剛剛遍歷的數字來組成一組，一定可以滿足條件。
因為遍歷用的數字不能滿足條件的有 sum 組，而這 sum 組被 t 恰好補充。

#include<bits/stdc++.h> using namespace std; struct p {int a, b;p() {}p(int a, int b) {this->a = a;this->b = b;} }; int n, m, a, b; int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> m;int v[n + 10];vector<p> arr;for (int i = 0; i < m; i++) {cin >> a >> b;arr.emplace_back(p(a, b));}vector<int> d = { arr[0].a,arr[0].b };for (int i : d) {memset(v, 0, sizeof v);int sum = 0;for (auto j : arr) {if (j.a != i && j.b != i) {sum++;v[j.a]++;v[j.b]++;}}int ma = *max_element(v + 1, v + n + 1);if (ma == sum) {cout << "YES" << endl;return 0;}}cout << "NO" << endl;return 0; }

總結

以上是生活随笔為你收集整理的Pairs的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。