No.8107 Listening
レベル :
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 28
作問者 :
harurun
/ テスター :
yuusanlondon
タグ : / 解いたユーザー数 28
作問者 :
harurun
/ テスター :
yuusanlondon
問題文最終更新日: 2024-03-07 05:25:21
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder April Fool Contest 2024
(順位表)
の他の問題:
Problem Statement
Input
$N\ M$ $u_1\ v_1$ $\vdots$ $u_M\ v_M$
- $2≤N≤2\times 10^5$
- $N-1≤M≤min(N(N-1)/2,10^6)$
- $1≤u_i,v_i≤N$
- $u_i\ne v_i$
- $i\ne j \Rightarrow \{u_i,v_i\}\ne \{u_j,v_j\}$
- All inputs are integers.
- The given graph is simple, undirected, and connected.
Output
Let $S$ be a set of edge indices satisfying the conditions in the problem statement.
$|S|$
$S_1$
$\vdots$
$S_{|S|}$
First, print the size of $S$ on the first line.
Then, print each edge index contained in $S$ exactly once, one per line.
If there are multiple answers, any of them will be accepted.
Sample
Sample 1
Input
4 6 1 2 1 3 1 4 2 3 2 4 3 4
Output
2 1 6
The given graph is as shown in the figure below.
The graph in the figure below is a maximum matching of the given graph. In this case, $S=\{1,6\}$.
The elements of $S$ may be printed in any order.
The following output is also accepted.
2 2 5
This output also gives a maximum matching of the given graph.
Sample 2
Input
5 5 1 2 2 3 3 4 4 5 5 2
Output
2 1 4
This output is a maximum matching of the given graph.
Sample 3
Input
6 5 1 2 6 2 6 3 6 4 6 5
Output
2 1 3
This output is a maximum matching of the given graph.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。