codeforces-scrape

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

673B.md (2484B)


      1 Source: https://codeforces.com/problemset/problem/673/B
      2 
      3 B. Problems for Round
      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 There are *n* problems prepared for the next Codeforces round. They are arranged in ascending order by their difficulty, and no two problems have the same difficulty. Moreover, there are *m* pairs of similar problems. Authors want to split problems between two division according to the following rules:
     22 
     23 * Problemset of each division should be non-empty.
     24 * Each problem should be used in exactly one division (yes, it is unusual requirement).
     25 * Each problem used in division 1 should be harder than any problem used in division 2.
     26 * If two problems are similar, they should be used in different divisions.
     27 
     28 Your goal is count the number of ways to split problem between two divisions and satisfy all the rules. Two ways to split problems are considered to be different if there is at least one problem that belongs to division 1 in one of them and to division 2 in the other.
     29 
     30 Note, that the relation of similarity is not transitive. That is, if problem *i* is similar to problem *j* and problem *j* is similar to problem *k*, it doesn't follow that *i* is similar to *k*.
     31 
     32 Input
     33 
     34 The first line of the input contains two integers *n* and *m* (2 ≤ *n* ≤ 100 000, 0 ≤ *m* ≤ 100 000) — the number of problems prepared for the round and the number of pairs of similar problems, respectively.
     35 
     36 Each of the following *m* lines contains a pair of similar problems *u**i* and *v**i* (1 ≤ *u**i*, *v**i* ≤ *n*, *u**i* ≠ *v**i*). It's guaranteed, that no pair of problems meets twice in the input.
     37 
     38 Output
     39 
     40 Print one integer — the number of ways to split problems in two divisions.
     41 
     42 Examples
     43 
     44 Input
     45 
     46 ```
     47 5 2  
     48 1 4  
     49 5 2
     50 ```
     51 
     52 Output
     53 
     54 ```
     55 2
     56 ```
     57 
     58 Input
     59 
     60 ```
     61 3 3  
     62 1 2  
     63 2 3  
     64 1 3
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 0
     71 ```
     72 
     73 Input
     74 
     75 ```
     76 3 2  
     77 3 1  
     78 3 2
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 1
     85 ```
     86 
     87 Note
     88 
     89 In the first sample, problems 1 and 2 should be used in division 2, while problems 4 and 5 in division 1. Problem 3 may be used either in division 1 or in division 2.
     90 
     91 In the second sample, all pairs of problems are similar and there is no way to split problem between two divisions without breaking any rules.
     92 
     93 Third sample reminds you that the similarity relation is not transitive. Problem 3 is similar to both 1 and 2, but 1 is not similar to 2, so they may be used together.