codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.