All Tracks Algorithms Graphs Depth First Search Problem

Matt's Graph Book
Tag(s):

Algorithms, Easy

Problem
Editorial
Analytics

Matt loves Graph Theory. He recently enrolled into the Algorithms course and started liking it too. His teacher understood his love for graphs and decided to give him a problem.

She gives him a Tree and asks him to write a program to find if it's connected or not. She realizes that Matt would do this in no time. So, instead she gives him a Graph and then removes a vertex from it and now asks him to find if the resultant graph is connected or not.

Since he is new to programming and algorithms, you have to help him solve this problem.

Input

First line contains a single integer N denoting the number of vertices in the graph. Second line contains a single integer k denoting the number of edges in the graph. k lines follow each containing two space separated integers a and b denoting the edge between the vertices a and b. Then, the last line contains a single integer x which denotes the vertex that is removed from the graph.

Output

"Connected" (without quotes) if the resultant graph is connected. "Not Connected" (without quotes), otherwise.

Constraints

1 ≤ N ≤ 105
1 ≤ k ≤ 2×105
0 ≤ a,b ≤ 105
0 ≤ x ≤ 105

SAMPLE INPUT
4
3
3 0
0 1
1 2
2
SAMPLE OUTPUT
Connected
Explanation

Number of vertices: 4
Number of edges: 3

enter image description here

It is still Connected.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Sabre

Challenge Name

Sabre Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications