AT_abc483_c.Second Choice Election

普及-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

AtCoder Village is holding an election to choose its mayor.
There are NN candidates, numbered candidate 11, candidate 22, …\ldots, candidate NN.

There are MM voters. The ii-th voter (1≤i≤M)(1\leq i\leq M) has candidate AiA_i as their first choice and candidate BiB_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,…,Nk=1,2,\ldots,N, find the number of the candidate who wins when only candidate kk withdraws.

AtCoder 村正在举行一场选举以选出村长。
共有 NN 位候选人,编号分别为候选人 11、候选人 22、…\ldots、候选人 NN。

共有 MM 名选民。第 ii 名选民(1≤i≤M1\leq i\leq M)的第一选择是候选人 AiA_i,第二选择是候选人 BiB_i。

当恰好一位候选人退选时,每名选民的投票规则如下:

  • 若该选民的第一选择候选人未退选,则该选民为其第一选择候选人投票;
  • 若该选民的第一选择候选人已退选,则该选民为其第二选择候选人投票。

在所有未退选的候选人中,得票数最多的候选人当选;若存在多名候选人得票数并列最多,则编号最小者当选。

对每个 k=1,2,…,Nk=1,2,\ldots,N,求出仅候选人 kk 退选时的当选候选人编号。

输入格式

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

NN MM
A1A_1 B1B_1
A2A_2 B2B_2
⋮\vdots
AMA_M BMB_M

输入从标准输入中按以下格式给出:

NN MM
A1A_1 B1B_1
A2A_2 B2B_2
⋮\vdots
AMA_M BMB_M

输出格式

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

输出 NN 行。第 ii 行应包含仅候选人 ii 退选时的获胜候选人编号。

输入输出样例

  • 输入#1

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

    输出#1

    3
    1
    1
    2
    1

说明/提示

Sample 1 Explanation:
When only candidate 11 withdraws, the voters vote as follows.

  • Voter 11's first-choice candidate has withdrawn, so they vote for their second-choice candidate, candidate 33.
  • Voter 22's first-choice candidate has withdrawn, so they vote for their second-choice candidate, candidate 33.
  • Voter 33's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 22.
  • Voter 44's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 22.
  • Voter 55's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 33.
  • Voter 66's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 44.

Thus, candidate 22 receives 22 votes, candidate 33 receives 33 votes, and candidate 44 receives 11 vote, so candidate 33, who has the most votes, wins.

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

  • When only candidate 22 withdraws, candidate 11 receives 44 votes, candidate 33 receives 11 vote, and candidate 44 receives 11 vote, so candidate 11, who has the most votes, wins.
  • When only candidate 33 withdraws, candidate 11 receives 22 votes, candidate 22 receives 22 votes, and candidate 44 receives 22 votes, so candidate 11, who has the smallest number among those with the most votes, wins.
  • When only candidate 44 withdraws, candidate 11 receives 22 votes, candidate 22 receives 33 votes, and candidate 33 receives 11 vote, so candidate 22, who has the most votes, wins.
  • When only candidate 55 withdraws, candidate 11 receives 22 votes, candidate 22 receives 22 votes, candidate 33 receives 11 vote, and candidate 44 receives 11 vote, so candidate 11, who has the smallest number among those with the most votes, wins.

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

Constraints

  • 2≤N≤2×1052 \leq N \leq 2\times 10^5
  • 1≤M≤2×1051 \leq M \leq 2\times 10^5
  • 1≤Ai,Bi≤N1 \leq A_i,B_i \leq N
  • Ai≠BiA_i\neq B_i
  • All input values are integers.

样例 1 解释:
当仅有候选人 11 退选时,选民的投票情况如下:

  • 选民 11 的首选候选人已退选,因此转而投票给其第二顺位候选人,即候选人 33。
  • 选民 22 的首选候选人已退选,因此转而投票给其第二顺位候选人,即候选人 33。
  • 选民 33 的首选候选人未退选,因此仍投票给其首选候选人,即候选人 22。
  • 选民 44 的首选候选人未退选,因此仍投票给其首选候选人,即候选人 22。
  • 选民 55 的首选候选人未退选,因此仍投票给其首选候选人,即候选人 33。
  • 选民 66 的首选候选人未退选,因此仍投票给其首选候选人,即候选人 44。

因此,候选人 22 获得 22 票,候选人 33 获得 33 票,候选人 44 获得 11 票,得票最多的候选人 33 当选。

当其余每位候选人分别单独退选时,结果如下:

  • 当仅有候选人 22 退选时,候选人 11 获得 44 票,候选人 33 获得 11 票,候选人 44 获得 11 票,因此得票最多的候选人 11 当选。
  • 当仅有候选人 33 退选时,候选人 11 获得 22 票,候选人 22 获得 22 票,候选人 44 获得 22 票,因此在得票最多的候选人中编号最小者(即候选人 11)当选。
  • 当仅有候选人 44 退选时,候选人 11 获得 22 票,候选人 22 获得 33 票,候选人 33 获得 11 票,因此得票最多的候选人 22 当选。
  • 当仅有候选人 55 退选时,候选人 11 获得 22 票,候选人 22 获得 22 票,候选人 33 获得 11 票,候选人 44 获得 11 票,因此在得票最多的候选人中编号最小者(即候选人 11)当选。

因此,按顺序输出 3,1,1,2,13,1,1,2,1,每行一个。

约束条件

  • 2≤N≤2×1052 \leq N \leq 2\times 10^5
  • 1≤M≤2×1051 \leq M \leq 2\times 10^5
  • 1≤Ai,Bi≤N1 \leq A_i,B_i \leq N
  • Ai≠BiA_i\neq B_i
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页