Log inSign up
Problems / B073

Swapping seats around

300 ptsCases 15Set by dongbinna
Added October 30.
1 solved1 attempted1 submissionssolvers took 1.0 tries on average

Statement

A reading room has n seats, and the seats are numbered 1 through n. Each seat carries one sign, and the sign holds the number of the seat that the person sitting there will move to. The number on a sign is a natural number from 1 to n, and signs on different seats may hold the same number, and a sign may hold the number of its own seat.

The manager wants to pick a few seats and have only the people sitting in the seats picked move at the same time to the seat their sign points to. After the move every seat picked has to hold exactly one person, and the seats that were not picked must not be touched. For that, the numbers of the seats picked, gathered together, and the numbers on the signs of the seats picked, gathered together, have to be the same. If even one of the seats picked has a sign pointing to a seat that was not picked, people crowd into that seat and the condition breaks.

Write a program that, given the signs, finds the largest number of seats that can be picked while meeting the condition above, together with the numbers of the seats picked in that case. The numbers of the seats picked are given from the smallest upward.

For example, suppose the signs of a reading room with n=7 are as in the table below.

Seat number1234567
Number on the sign3115546

Picking seats 1, 3 and 5 meets the condition here. The numbers of the seats picked gather into 1, 3 and 5, and the numbers on the signs of the seats picked are the 3 of seat 1, the 1 of seat 3 and the 5 of seat 5, which again gather into 1, 3 and 5.

Seat picked135
Number on the sign315

Adding seat 2 to these would put 1 into the numbers on the signs twice, so two people crowd into seat 1 and the condition breaks. Adding seat 4 or seat 6 or seat 7 brings in a sign that points to a seat which was not picked. So the largest number of seats that can be picked in this example is 3, and their numbers from the smallest upward are 1, 3 and 5.

Input and Output Examples

Example 1

Input

7
3
1
1
5
5
4
6

Output

3
1
3
5

Example 2

Input

3
3
3
2

Output

2
2
3

Example 3

Input

7
3
4
5
5
2
3
2

Output

3
2
4
5

Input

  • First the number of seats n is given on the first line. n is a natural number from 1 to 100.

  • Next the numbers on the signs of seats 1 through n are given over n lines, one per line, in order. That is, the second line is the sign of seat 1 and the third line is the sign of seat 2. Each number is a natural number from 1 to n, and the same number can appear on several lines.

Output

  • Print the largest number of seats that can be picked while meeting the condition on the first line. Then print the numbers of the seats picked in that case, from the smallest upward, one per line.

Requirements

  • The numbers of the seats picked, gathered together, and the numbers on the signs of the seats picked, gathered together, have to be the same
  • The seats that were not picked are not touched
  • Find the case with the largest number of seats that can be picked while meeting the condition
  • Write the count on the first line, and after it the numbers of the seats picked from the smallest upward, one per line
  • You must write a program that reads from standard input and writes to standard output
  • Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
  • The languages you can use are Python and JavaScript
  • The memory limit is 256MB. The browser does not measure it, it only states it
  • The time limit is set by measuring the setter's reference solution on the same runtime
  • On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
  • The output has to match the expected value down to the character. A space inside a line counts the same as any other character.
  • There are 15 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
  • You have to pass all 15 cases to solve this.
Read the requirements carefully before solving. Tampering with the grading to make a submission look like a pass can get you sanctioned if caught. The code you submit is published on the leaderboard along with the result.

Examples

3 public cases. Judging also uses hidden cases. You have to pass all 15 cases to solve this.

Input
Expected output
3
3
3
2
2
2
3
7
3
4
5
5
2
3
2
3
2
4
5
7
3
1
1
5
5
4
6
3
1
3
5

Solution

Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.

0 chars1 lineMemory 256MB (recorded only)Reference 3.0ms

Submitting requires you to log in. Running against the public cases works without one.

You can test with 3 public cases. Submitting runs the hidden cases too.

People who solved this problem

The time shown is the time spent solving. Input reading time is outside the solver's control, so it is excluded. And since each device reports this value itself, we record which device measured it.

1bampal244ms475 charsPythonWindows NT 10.0 / Chrome/156.0.0.0 / 8코어 / 16GB

Log in and you can see the code once you solve this problem.