" " "
Q: Uầyyy bầu trời hôm nay đẹp vậy!!
Q: Này này cậu nhìn những vì sao kia kìa đẹp thật đấy
C: Đúng đúng đúng
Q: Nếu tớ có khả năng nối những vì sao ấy lại thì chuyện gì sẽ xảy ra nhỉ?
" " "

Vấn đề này có thể được gọi là trò chơi nối sao của Q và C. Trong một đêm cả hai cùng ngước nhìn lên thì họ nhìn thấy trước mắt mình là một bầu trời với ~N~ ngôi sao đang tỏa sáng lấp lánh, những ngôi sao này được Q gọi là những ngôi sao cô đơn. Vì vậy, cậu ấy đã tưởng tượng ra một đường thẳng để nối hai ngôi sao ấy lại với nhau. Nhưng cậu ấy lại lo sợ rằng đường thẳng mình vừa vẽ sẽ biến mất và những ngôi sao ấy lại phải cô đơn một lần nữa, Q tự gọi những đường thẳng này là cạnh cầu, cạnh cầu là cạnh mà khi xóa đi sẽ tăng số lượng ngôi sao cô đơn (theo học thuyết của Q). Vì vậy cậu ấy đã quay sang hỏi C là sau khi mà cậu ấy nối hai ngôi sao bất kỳ lại thì sẽ có bao nhiêu cạnh cầu và nếu mà C không trả lời được thì Q sẽ mãi nằm ở đây vẽ vẽ @@. Vì mãi lo ngắm Q nên C không thể nào trả lời được câu hỏi này, bạn hãy giúp cậu ấy nhé.

Input:

• Dòng đầu tiên gồm hai số nguyên ~N~ và ~M~ cho biết số ngôi sao và số câu hỏi của Q dành cho C với ~2 \le N \le 10^5~ và ~1 \le M \le 2 \cdot 10^5.~

• ~M~ dòng tiếp theo bao gồm hai số nguyên ~u~ và ~v~ nghĩa là Q sẽ nối ngôi sao thứ ~u~ và ngôi sao thứ ~v~ lại với nhau, trong đó ~1 \le u, v \le N.~

• Dữ liệu đảm bảo rằng không có hai ngôi sao nối với nhau nhiều hơn ~1~ lần và sẽ không có ngôi sao nào tự nối với chính nó và các ngôi sao này sẽ được Q đánh số từ ~1~ đến ~N~.

Output:

Với mỗi câu hỏi của Q, bạn hãy nói cho C biết số cạnh cầu hiện tại mà cậu ấy đã vẽ.

Sample Input

7 9
1 6
1 3
6 3
3 6
6 5
5 3
2 7
7 4
4 2

Sample Output

1
2
0
0
1
0
1
2
0

---