C - Second Choice Election Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

AtCoder 村で村長を決める投票を行うことになりました。
候補者は N 人おり、候補者 1, 候補者 2, \ldots, 候補者 N と番号づけられています。

投票者は M 人おり、i 人目 (1\leq i\leq M) の投票者の投票先の第一希望は候補者 A_i、第二希望は候補者 B_i です。

候補者のうち一人のみが辞退した時、それぞれの投票者は以下のように投票します。

  • 第一希望の候補者が辞退していなければ、第一希望の候補者に投票する。
  • 第一希望の候補者が辞退していれば、第二希望の候補者に投票する。

辞退していない候補者のうち、得票数が最大の候補者が当選します。そのような候補者が複数いる場合は、番号が最小の候補者が当選します。

k=1,2,\ldots,N それぞれについて、候補者 k のみが辞退した場合に当選する候補者の番号を求めてください。

制約

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 1 \leq A_i,B_i \leq N
  • A_i\neq B_i
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

N 行出力せよ。i 行目には、候補者 i のみが辞退した場合に当選する候補者の番号を出力せよ。

入力例 1

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

出力例 1

3
1
1
2
1

候補者 1 のみが辞退した場合、それぞれの投票者の投票先は次のようになります。

  • 投票者 1 の第一希望の候補者は辞退しているため、第二希望の候補者 3 に投票する。
  • 投票者 2 の第一希望の候補者は辞退しているため、第二希望の候補者 3 に投票する。
  • 投票者 3 の第一希望の候補者は辞退していないため、第一希望の候補者 2 に投票する。
  • 投票者 4 の第一希望の候補者は辞退していないため、第一希望の候補者 2 に投票する。
  • 投票者 5 の第一希望の候補者は辞退していないため、第一希望の候補者 3 に投票する。
  • 投票者 6 の第一希望の候補者は辞退していないため、第一希望の候補者 4 に投票する。

よって得票数は、候補者 2 が 2 票、候補者 3 が 3 票、候補者 4 が 1 票となり、このとき得票数が最大の候補者 3 が当選します。

他の候補者が辞退した時はそれぞれ以下のようになります。

  • 候補者 2 のみが辞退した時、候補者 1 が 4 票、候補者 3 が 1 票、候補者 4 が 1 票となり、得票数が最大の候補者 1 が当選します。
  • 候補者 3 のみが辞退した時、候補者 1 が 2 票、候補者 2 が 2 票、候補者 4 が 2 票となり、得票数が最大の候補者のうち番号が最小の候補者 1 が当選します。
  • 候補者 4 のみが辞退した時、候補者 1 が 2 票、候補者 2 が 3 票、候補者 3 が 1 票となり、得票数が最大の候補者 2 が当選します。
  • 候補者 5 のみが辞退した時、候補者 1 が 2 票、候補者 2 が 2 票、候補者 3 が 1 票、候補者 4 が 1 票となり、得票数が最大の候補者のうち番号が最小の候補者 1 が当選します。

よって、3,1,1,2,1 をこの順に各行に出力します。

Score : 300 points

Problem Statement

AtCoder Village is holding an election to choose its mayor.
There are N candidates, numbered candidate 1, candidate 2, \ldots, candidate N.

There are M voters. The i-th voter (1\leq i\leq M) has candidate A_i as their first choice and candidate B_i as their second choice.

When exactly one of the candidates withdraws, each voter votes as follows.

  • If the voter's first-choice candidate has not withdrawn, the voter votes for their first-choice candidate.
  • If the voter's first-choice candidate has withdrawn, the voter votes for their second-choice candidate.

Among the candidates who have not withdrawn, the candidate with the most votes wins. If there are multiple such candidates, the one with the smallest number wins.

For each k=1,2,\ldots,N, find the number of the candidate who wins when only candidate k withdraws.

Constraints

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 1 \leq A_i,B_i \leq N
  • A_i\neq B_i
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

Print N lines. The i-th line should contain the number of the candidate who wins when only candidate i withdraws.

Sample Input 1

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

Sample Output 1

3
1
1
2
1

When only candidate 1 withdraws, the voters vote as follows.

  • Voter 1's first-choice candidate has withdrawn, so they vote for their second-choice candidate, candidate 3.
  • Voter 2's first-choice candidate has withdrawn, so they vote for their second-choice candidate, candidate 3.
  • Voter 3's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 2.
  • Voter 4's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 2.
  • Voter 5's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 3.
  • Voter 6's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 4.

Thus, candidate 2 receives 2 votes, candidate 3 receives 3 votes, and candidate 4 receives 1 vote, so candidate 3, who has the most votes, wins.

When each of the other candidates withdraws instead, the results are as follows.

  • When only candidate 2 withdraws, candidate 1 receives 4 votes, candidate 3 receives 1 vote, and candidate 4 receives 1 vote, so candidate 1, who has the most votes, wins.
  • When only candidate 3 withdraws, candidate 1 receives 2 votes, candidate 2 receives 2 votes, and candidate 4 receives 2 votes, so candidate 1, who has the smallest number among those with the most votes, wins.
  • When only candidate 4 withdraws, candidate 1 receives 2 votes, candidate 2 receives 3 votes, and candidate 3 receives 1 vote, so candidate 2, who has the most votes, wins.
  • When only candidate 5 withdraws, candidate 1 receives 2 votes, candidate 2 receives 2 votes, candidate 3 receives 1 vote, and candidate 4 receives 1 vote, so candidate 1, who has the smallest number among those with the most votes, wins.

Thus, print 3,1,1,2,1 in this order, one per line.