Problem Description

Joisino's next job is to assist a debugger. The debugger has just discovered a bug but forgot the exact conditions to reproduce it. Therefore, they are considering trying all methods that match the conditions they remember.

The conditions are as follows:

1. This game has $ N $ villages and $ M $ bidirectional roads that connect two different villages. There is no way to travel from one village to another without using these roads.
2. Villages are numbered from $ 1 $ to $ N $, and no two villages are directly connected by more than one road.
3. When the bug was reproduced, the debugger started from one village and moved to different villages 4 times.
4. During this process, no village was visited more than once.
   To estimate the debugging time, the debugger wants to know, for each village, how many possible paths there are if they start from that village. Joisino's task is to write a program that calculates the number of possible paths for each village if they start from there.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ : $ A_M $ $ B_M $

• The first line contains two integers, $ N(1 ≦ N ≦ 10^5) $, representing the number of villages, and $ M(1 ≦ M ≦ 10^5) $, representing the number of roads.
• The following $ M $ lines each contain two integers $ A_i(1 ≦ A_i ≦ N) $ and $ B_i(1 ≦ B_i ≦ N) $, indicating that the $ i $-th road directly connects village $ A_i $ and village $ B_i $.

Output Format

The output consists of $ N $ lines.
The $ i $-th line should contain the number of possible paths if starting from village $ i $.

Sample Input and Output

Sample Input #1

6 8
1 2
2 3
5 2
1 5
3 4
5 3
5 6
5 4

Sample Output #1

7
4
4
7
2
4

Sample Input #2

6 15
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6

Sample Output #2

120
120
120
120
120
120

Sample Input #3

8 11
3 6
7 8
8 5
4 5
2 1
2 6
3 2
4 3
5 3
6 5
7 6

Sample Output #3

12
14
11
17
11
9
15
17

Notes/Hints

Scoring

This problem has partial scoring.

1. Dataset 1 satisfies $ N(1 ≦ N ≦ 100) $ and awards 10 points for a correct answer.
2. Dataset 2 has no additional constraints and awards 130 points for a correct answer.

Sample Explanation 1

For example, if starting from village 1, the following 7 paths are possible:
1. $ 1→2→3→4→5 $
2. $ 1→2→3→5→4 $
3. $ 1→2→3→5→6 $
4. $ 1→2→5→3→4 $
5. $ 1→2→5→4→3 $
6. $ 1→5→2→3→4 $
7. $ 1→5→4→3→2 $

见题面 Input 部分

见题面 Output 部分