CF19E.Fairy
省选/NOI-
通过率:0%
时间限制:1.50s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Once upon a time there lived a good fairy A. One day a fine young man B came to her and asked to predict his future. The fairy looked into her magic ball and said that soon the fine young man will meet the most beautiful princess ever and will marry her. Then she drew on a sheet of paper n points and joined some of them with segments, each of the segments starts in some point and ends in some other point. Having drawn that picture, she asked the young man to erase one of the segments from the sheet. Then she tries to colour each point red or blue so, that there is no segment having points of the same colour as its ends. If she manages to do so, the prediction will come true. B wants to meet the most beautiful princess, that's why he asks you to help him. Find all the segments that will help him to meet the princess.
从前,住着一位善良的仙女 A。一天,一位英俊的年轻人 B 来到她面前,请她预言自己的未来。仙女凝视她的魔法水晶球,说道:“不久之后,这位英俊的年轻人将遇见有史以来最美丽的公主,并与她结婚。”接着,她在一张纸上画出了 n 个点,并用若干条线段连接其中一些点;每条线段都始于某一点并终于另一点。画完这幅图后,她让年轻人擦去纸上的一条线段。然后,她尝试将每个点染成红色或蓝色,使得任意一条线段的两个端点颜色均不相同。若她能成功完成这种染色,则预言便会成真。B 渴望遇见那位最美丽的公主,因此他请你帮助他:找出所有能使预言成真的、可被擦去的线段(即擦去该线段后,剩余图形是二分图的所有线段)。
输入格式
The first input line contains two integer numbers: n — amount of the drawn points and m — amount of the drawn segments (1 ≤ n ≤ 104, 0 ≤ m ≤ 104). The following m lines contain the descriptions of the segments. Each description contains two different space-separated integer numbers v, u (1 ≤ v ≤ n, 1 ≤ u ≤ n) — indexes of the points, joined by this segment. No segment is met in the description twice.
第一行输入包含两个整数:n —— 所绘制的点的数量,以及 m —— 所绘制的线段的数量(1 ≤ n ≤ 104,0 ≤ m ≤ 104)。接下来的 m 行描述这些线段。每行描述包含两个用空格分隔的不同整数 v、u(1 ≤ v ≤ n,1 ≤ u ≤ n),表示该线段所连接的两个点的索引。任意一条线段在输入中至多出现一次。
输出格式
In the first line output number k — amount of the segments in the answer. In the second line output k space-separated numbers — indexes of these segments in ascending order. Each index should be output only once. Segments are numbered from 1 in the input order.
第一行输出数字 k —— 答案中线段的数量。
第二行输出 k 个用空格分隔的数字 —— 这些线段在输入中的索引(按升序排列)。每个索引仅输出一次。线段按输入顺序从 1 开始编号。
输入输出样例
输入#1
4 4 1 2 1 3 2 4 3 4
输出#1
4 1 2 3 4
输入#2
4 5 1 2 2 3 3 4 4 1 1 3
输出#2
1 5
输入解题思路,AI测评打分。不知道怎么写?