| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 83 | 30 | 27 | 36.486% |
Boss, if $N≤30,円 000,ドル you should try to optimise the $N^2$ solution. (Friedrich Nietzsche)
Let $G$ be a undirected connected graph with $N$ nodes and $M$ edges. Label each of the $M$ edges with a distinct integer from 1ドル$ to $M$. For each node with degree greater than 1ドル,ドル the greatest common divisor of its incident edges' labels should be 1ドル$.
The first line contains two integers $N$ and $M$.
The next $M$ lines contain two integers $u$ and $v,ドル representing two nodes that share an edge.
Print $M$ lines, each containing three integers $u,ドル $v$ and $c$ corresponding to an edge with label $c$ between $u$ and $v$.
5 6 1 2 2 3 1 3 4 1 3 4 3 5
1 2 2 1 4 1 1 3 3 3 2 5 3 4 4 3 5 6
$G$ has 5ドル$ nodes and 6ドル$ edges.
The labels for node 1ドル$ are $\{2,1,3\}$.
The labels for node 2ドル$ are $\{2,5\}$.
The labels for node 3ドル$ are $\{3,4,5,6\}$.
The labels for node 4ドル$ are $\{1,4\}$.
Node 5ドル$ has degree 1ドル$.