# STP1TN - EDITORIAL

Contest

Setter: debrc

Tester: mishra_roshan

Editorialist: debrc

Easy-Medium

# PREREQUISITES:

Basic observations, Set

# PROBLEM:

Given A number of nodes and B number of edges, find out if Node 1 and Node A are exactly two edges away.

# EXPLANATION

If there is at least one common node to which Node 1 and Node A both are connected through a edge, then both the node are exactly two edges away.

So we can make two sets,
one set contains the nodes to which Node 1 is connected and
one set contains the nodes to which Node A is connected.

If the bitwise and of both the sets leads to True then there has to be at least one common node in both the sets.
Otherwise, no common nodes are there, hence Node 1 and Node A are not two edges away.

# TIME COMPLEXITY

Time complexity is O(A) for making the set.

# SOLUTIONS:

Setter's Solution
Python
``````a,b=map(int,input().split())
node1,noden=[],[]
for i in range(b):
u,v=map(int,input().split())
if u==1:
node1.append(v)
if v==a:
noden.append(u)
if set(node1)&set(noden):
print("YES")
else:
print("NO")
``````
Tester's Solution
Java
``````import java.util.*;

public class Main {

static void bfs(int node,int[] dis){
dis[node]=0;
while(q.size()>0){
int curr=q.poll();
if(dis[child]==-1){
dis[child]=dis[curr]+1;
}
}
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
int b=sc.nextInt();
for(int i=0;i<=a;i++)
for(int i=1;i<=b;i++){
int u=sc.nextInt();
int v=sc.nextInt();

}
int[] dis=new int[a+1];
Arrays.fill(dis,-1);
bfs(1,dis);
if(dis[a]>2 || dis[a]==-1)
System.out.println("NO");
else
System.out.println("YES");

}

}
``````

Feel free to Share your approach.
Suggestions are welcomed as always had been.