Déjà vu

Program time limit: 3 seconds

Program memory limit: 256 MB

Déjà vu? Sometimes even the greatest poets write stuff that looks similar to what they’ve written before. No one knows what this could mean. I Might just be Ceeing too much into this. Wait, don’t I write "see" with an s? Maybe it’s fine if I leave it as is, since I’m a great poet.

Input

The first line contains two integers $N$ and $M$.
The next $M$ lines each contain two integers $A_i$ and $B_i$.

You should read from standard input.

Constraints

$2 \le N \le 10^5$
$1 \le M \le \min(N(N-1), 3 \cdot 10^5)$
$1 \le A_i, B_i \le N$
$A_i \ne B_i$
$(A_i, B_i) \ne (A_j, B_j)$ for $i \ne j$

Output

Print $M$ lines.
On the $i$-th line, print the answer.

You should write to standard output.

Sample Input

Sample Output

Scoring

Your program will be tested on the sample case and several hidden cases. If it produces the correct output for all test cases, it will be considered correct. Recall that your final score for this problem is the score of your highest-scoring submission.

Submit unofficially

The contest ended at 8:45 p.m. AEST on Tuesday 7th April. All submissions will be unofficial officially.