1. Dead Pod Recovery (Easy)

A system has n serving pods numbered from 1 to n distributed across multiple geographical regions. These pods are interconnected by m links, represented by the array connections. If two pods are connected directly or indirectly, they belong to the same region.

Each pod has a database connection where it writes the critical data received. If a pod loses its database connection, it forwards the data to the active pod in the same region that has the lowest ID, and that pod writes the data to the region's database. If there are no active pods left in the region, the data is not written, and an error is recorded in the logs.

Process q queries of two types:

⚫ a data-sending query of the form "1 pod_id,"

⚫ a database-connection-failure query of the form "2 pod_id"

Return an integer array with an element for each data-sending quer The value is either the ID of the pod where data is ultimately written, or -1 if it cannot be written.

Example

Suppose n = 3, m = 2, connections = [[1, 2], [2, 3]], q = 5, queries = [[2,2], [1, 2], [2, 1], [2, 3], [1, 1]]

Query

Pod Losing Connection

2

Result

Remarks

1

2,2

1,2

Since two lost its connected, the lowest Id pod in the region is 1

2,1

2,3

1,1

1

3

-1

No pod is in the network

Hence the answer returned is [1, -1].

Function Description

Complete the function recoverDeadPods in the editor below.

recover DeadPods has the following parameters:

int n: the number of pods

int connections[m][2]: the connections between pods

int queries[q][2]: the queries

Returns

int[]: the answer to the queries

Constraints

• 1≤≤103

• 0≤m≤103

• 1≤q≤ 2x103

1 ≤ connections[i][0], connections[i][1]≤ n

• 1 ≤ queries[i][0] ≤ 2

• 1 ≤ queries[i] [1] ≤ n

There is at least 1 query of type 1.

▼Input Format For Custom Testing

The first line contains an integer, n, the number of pods. The next line contains an integer, m, the number of connections. The next line contains an integer, 2, the number of integers required to describe a connection.

Each line / of the m subsequent lines (where Osi<m) contains two space-separated integers, connections[i][0], and connections[i][1].

The next line contains an integer, q, the number of queries. The next line contains an integer, 2, the number of integers required to describe a query.

Each line / of the q subsequent lines (where 0≤i<q) contains two space-separated integers, queries[i][0] ar queries[i][1].

▼ Sample Case 0

Sample Input For Custom Testing

STDIN

FUNCTION

2

1

2

12

1

2

12

→

→

Sample Output

connections[] size m = 1

connections[] [] size constant = 2

connections = [[1, 2]]

queries[] size q = 1

queries[][] size constant = 2

queries = [[1, 2]]

2

Explanation For the only query pod, 2 sends the message through pod 2.

▼Sample Case 1

Sample Input For Custom Testing

connections[] size \mathfrak{m} = 4

connections [] size constant = 2

connections = [[1, 2], [2, 3], [1, 4],

STDIN

FUNCTION

4

→

4

→

2

→

12

→

[4,3]]

23

14

43

4

→

2

→

23

→

1]]

13

21

11

Sample Output

1

queries[] size q = 4

queries[][] size constant

2

queries [[2, 3], [1, 3], [2, 1], [1,

2

Explanation

After 3 loses connection, it sends the message via pod 1. After 1 loses connection, message is sent through 2.