## A Noisy Class

View as PDF

Points: 7
Time limit: 0.5s
Memory limit: 128M

Author:
Problem type

One day Mr. Sidhu's class is excessively loud. Unfortunately, giving them an activity about tiles didn't really work.

He notices that when he tells a certain student to stop talking, they will immediately resume since another noisy student will distract them, but if he tells the noisy student to stop talking, there will be silence at last.

After many hours of careful observations, Mr. Sidhu has given you a list containing the connections between students and asks you if it is even possible for the class to be completely silent.

Given the size of his class (as seen in New Students), he can only tell students to stop talking individually. Note that connections are in one direction - the noisy students talk to the distracted students, but not the other way around.

#### Input Specification

The first line consists of , the number of students; each student is assigned a number from to .
The next line contains , the number of connections.
The next lines contain two space-separated integers, representing the noisy student and the distracted student respectively. Given the sheer size, it is not guaranteed that the connections are distinct.

#### Output Specification

You are to output Y if it is possible and N if it is not.

#### Sample Input 1

4
4
1 2
2 3
2 4
4 3

#### Sample Output 1

Y

#### Explanation for Sample Output 1

Mr. Sidhu can tell the students to stop talking in the following order:

#### Sample Input 2

2
2
1 2
2 1

#### Sample Output 2

N

#### Explanation for Sample Output 2

After telling student to quiet down student will immediately distract him, and vice-versa. Since there is a cycle the class will never be quiet!

• commented on Jan. 19, 2021, 6:53 p.m.

I'm getting segmentation fault on test case 1 but my code is working fine on my computer on the sample test cases.

• commented on Dec. 27, 2020, 2:10 p.m.

I'm getting a WA on case #5. I used an adjacency list, but I'm not sure where I'm going wrong.

• commented on May 16, 2020, 5:50 p.m.
• commented on April 11, 2020, 11:13 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on April 16, 2018, 7:26 p.m.

the problem gives IR and in the bracket it says "OK!". I looked in the status codes page but I have no idea what's wrong. My code gets both samples correct.

• commented on Nov. 19, 2017, 4:19 p.m. edited

UPD Fixed Thanks

• commented on Nov. 19, 2017, 7:29 p.m.

The graph may not be connected.

• commented on April 28, 2015, 11:23 p.m.

The test data contains at least one case where the same edge is listed twice.

• commented on May 18, 2019, 2:36 p.m. edit 2

Why does it matter ? I have AC but didn't take that case into consideration.

• commented on April 29, 2015, 6:10 p.m.

It was initially not stated whether the edges are all distinct; the problem statement has been updated to clarify that this is not guaranteed.