codeforces-scrape

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

1009D.md (1790B)


      1 Source: https://codeforces.com/problemset/problem/1009/D
      2 
      3 D. Relatively Prime Graph
      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 Let's call an undirected graph $G = (V, E)$ relatively prime if and only if for each edge $(v, u) \in E$  $GCD(v, u) = 1$ (the greatest common divisor of $v$ and $u$ is $1$). If there is no edge between some pair of vertices $v$ and $u$ then the value of $GCD(v, u)$ doesn't matter. The vertices are numbered from $1$ to $|V|$.
     22 
     23 Construct a relatively prime graph with $n$ vertices and $m$ edges such that it is connected and it contains neither self-loops nor multiple edges.
     24 
     25 If there exists no valid graph with the given number of vertices and edges then output "Impossible".
     26 
     27 If there are multiple answers then print any of them.
     28 
     29 Input
     30 
     31 The only line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$) — the number of vertices and the number of edges.
     32 
     33 Output
     34 
     35 If there exists no valid graph with the given number of vertices and edges then output "Impossible".
     36 
     37 Otherwise print the answer in the following format:
     38 
     39 The first line should contain the word "Possible".
     40 
     41 The $i$-th of the next $m$ lines should contain the $i$-th edge $(v_i, u_i)$ of the resulting graph ($1 \le v_i, u_i \le n, v_i \neq u_i$). For each pair $(v, u)$ there can be no more pairs $(v, u)$ or $(u, v)$. The vertices are numbered from $1$ to $n$.
     42 
     43 If there are multiple answers then print any of them.
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 5 6
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 Possible  
     57 2 5  
     58 3 2  
     59 5 1  
     60 3 4  
     61 4 1  
     62 5 4
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 6 12
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 Impossible
     75 ```
     76 
     77 Note
     78 
     79 Here is the representation of the graph from the first example: ![](https://espresso.codeforces.com/501a835f442401d928aaaee2ff94c95a4900a18e.png)