Assignment 1: Graph Traversal (BFS & DFS)

Problem Description

You are given an undirected graph representing connections between buildings in a university campus.

Starting from a specified building, perform:

• Breadth First Search (BFS) traversal
• Depth First Search (DFS) traversal

Vertices should be visited in ascending numerical order when multiple choices are available.

Input/output

Input Format

1
2
3
4
5
6
N M
u1 v1
u2 v2
...
uM vM
S

Where:

• N — number of vertices (0 -> N-1)
• M — number of edges
• ui vi — undirected edge between vertex ui and vi
• S — starting vertex

Constraints:

• 1 ≤ N ≤ 1000
• 0 ≤ M ≤ 5000

Output Format: Two lines

1
2
BFS: v1 v2 v3 ...
DFS: v1 v2 v3 ...

Example

Input

1
2
3
4
5
6
7
5 5
0 1
0 2
1 3
2 4
3 4
0

Output

1
2
BFS: 0 1 2 3 4
DFS: 0 1 3 4 2

Assignment 2: Cycle Detection in Graph

Problem Description

A city road network is represented as an undirected graph.

Your task is to determine whether the network contains any cycle.

If a cycle exists, print YES, otherwise print NO.

You may use either:

• DFS-based cycle detection
• Union-Find
• BFS with parent tracking

Input/output

Input Format

1
2
3
4
5
N M
u1 v1
u2 v2
...
uM vM

Where

• 1 ≤ N ≤ 1000
• 0 ≤ M ≤ 5000

Output Format

YES or NO

Example

Input

1
2
3
4
5
4 4
0 1
1 2
2 3
3 1

Output

1
YES

Assignment 3: Shortest Path (Dijkstra)

Problem Description

A company network contains several buildings connected by communication cables.

Each cable has a transmission cost.

Find the minimum transmission cost from building 0 to all other buildings.

If a building is unreachable, print INF.

###

Input Format

1
2
3
4
5
N M
u1 v1 w1
u2 v2 w2
...
uM vM wM

Where

• N — number of vertices
• M — number of edges
• ui vi wi — edge from ui to vi with weight wi

Constraints:

• 1 ≤ N ≤ 1000
• 0 ≤ M ≤ 10000
• 1 ≤ wi ≤ 1000

Graph is directed.

Output Format: Single line

1
d0 d1 d2 ... d(N-1)

Where di is the shortest distance from node 0 to node i.

Example

Input

1
2
3
4
5
6
7
5 6
0 1 10
0 2 3
1 2 1
2 1 4
2 3 2
3 4 7

Output

1
0 7 3 5 12

Assignment 4: Minimum Spanning Tree (MST)

Problem Description

A company wants to connect all its buildings using network cables.

The cost of installing cables between buildings is given.

Find the minimum total cost required so that all buildings are connected.

You may implement either:

• Kruskal Algorithm
• Prim Algorithm

Input Format

1
2
3
4
5
N M
u1 v1 w1
u2 v2 w2
...
uM vM wM

Where

• N — number of vertices
• M — number of edges
• ui vi wi — undirected weighted edge

Constraints:

• 1 ≤ N ≤ 1000
• 0 ≤ M ≤ 10000

Output Format

1
Minimum Cost: X

If the graph is not connected, output:

1
IMPOSSIBLE

Example

Input

1
2
3
4
5
6
4 5
0 1 10
0 2 6
0 3 5
1 3 15
2 3 4

Output

1
Minimum Cost: 19