1169B.md (1626B)
1 Source: https://codeforces.com/problemset/problem/1169/B 2 3 B. Pairs 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Toad Ivan has $m$ pairs of integers, each integer is between $1$ and $n$, inclusive. The pairs are $(a_1, b_1), (a_2, b_2), \ldots, (a_m, b_m)$. 22 23 He asks you to check if there exist two integers $x$ and $y$ ($1 \leq x \lt y \leq n$) such that in each given pair at least one integer is equal to $x$ or $y$. 24 25 Input 26 27 The first line contains two space-separated integers $n$ and $m$ ($2 \leq n \leq 300\,000$, $1 \leq m \leq 300\,000$) — the upper bound on the values of integers in the pairs, and the number of given pairs. 28 29 The next $m$ lines contain two integers each, the $i$-th of them contains two space-separated integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n, a_i \neq b_i$) — the integers in the $i$-th pair. 30 31 Output 32 33 Output "YES" if there exist two integers $x$ and $y$ ($1 \leq x \lt y \leq 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). 34 35 Examples 36 37 Input 38 39 ``` 40 4 6 41 1 2 42 1 3 43 1 4 44 2 3 45 2 4 46 3 4 47 ``` 48 49 Output 50 51 ``` 52 NO 53 ``` 54 55 Input 56 57 ``` 58 5 4 59 1 2 60 2 3 61 3 4 62 4 5 63 ``` 64 65 Output 66 67 ``` 68 YES 69 ``` 70 71 Input 72 73 ``` 74 300000 5 75 1 2 76 1 2 77 1 2 78 1 2 79 1 2 80 ``` 81 82 Output 83 84 ``` 85 YES 86 ``` 87 88 Note 89 90 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. 91 92 In the second example, you can choose $x=2$ and $y=4$. 93 94 In the third example, you can choose $x=1$ and $y=2$.