Nabeel’s Confession Order
Time: 1 s
Memory: 125 MB
Memory: 125 MB
Nabeel Ahsan from CSE Batch-15 has been fined with a jorimana for low attendance.To receive a moukuf (waiver), he must collect a approval from every teacher in the department.
However, the department has politics. Each teacher has personal preferences—some will only give their approval after Nabeel meets another specific teacher first.
For example:
If Teacher A requires that Nabeel visits Teacher B beforehand, then the dependency is:
B → A
This creates a dependency relationship.If Nabeel violates any dependency rule, that teacher will refuse to confess, making the moukuf impossible.
You are given:
However, the department has politics. Each teacher has personal preferences—some will only give their approval after Nabeel meets another specific teacher first.
For example:
If Teacher A requires that Nabeel visits Teacher B beforehand, then the dependency is:
B → A
This creates a dependency relationship.If Nabeel violates any dependency rule, that teacher will refuse to confess, making the moukuf impossible.
You are given:
- n — number of teachers
- m — number of dependency rules
- Each rule a b means:
Teacher a requires Nabeel to visit teacher b first, so b → a.
Your task is to determine whether there exists an order in which Nabeel can visit all teachers while satisfying all dependencies.
Input
The first line contains two integers n and m — the number of teachers and the number of dependency rules.Each of the next m lines contains two integers a and b, meaning:
Teacher 'a' requires Nabeel to visit teacher 'b' first.
Constraint
\(1 \le n \le 10^5\)\(1 \le m \le 2 \cdot 10^5\)
\(1 \le a,b \le n\)
Output
If it is possible to satisfy all teachers’ requirements, print: "Confessed"If it is impossible , print: "Not Confessed"
Examples
| Input | Output |
|---|---|
|
4 2
2 1 4 3 |
Confessed
|
Notes
Explanation : For the given input, there are 4 teachers and 2 dependency rules. The rule “2 1” means Nabeel must visit teacher 1 before teacher 2, and the rule “4 3” means he must visit teacher 3 before teacher 4. These two conditions do not conflict with each other because they involve different pairs of teachers. So Nabeel can easily arrange his visits in an order that satisfies both requirements—for example, he can visit teachers in the order 1 → 2 → 3 → 4. Since at least one valid ordering exists that obeys all rules, it is possible for Nabeel to collect all the confessions. Therefore, the correct output is “Confessed.”
Problem Info
| Problem ID | 794 |
| Time Limit | 1000 ms |
| Memory Limit | 128000 KB |
| Moderators | Nabeel_Ahsan , tamjid_hossen , shazidmashrafi |
Statistics
Submit
You need to Login or Registration for submit your solution