You are given n nodes labeled from 0 to n-1, together with a set of undirected connections represented as pairs of nodes. It will be a string array and you will have to parse each row to fetch the nodes which are connected.

Write a method that determines whether the provided connections form a valid tree.

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0,1] is the same as [1,0] and thus will not appear together in edges.

Examples

Example 1:
Input: n = 4, connections = ["0 1", "0 2", "1 3"]
Output: true

Example 2:
Input: n = 4, connections = ["0 1", "1 2", "2 3", "1 3"]
Output: false

Example 3:
Input: n = 3, connections = ["0 1", "1 2"]
Output: true

Constraints

• 1 ≤ n ≤ 3000
• 0 ≤ connections.length ≤ n * (n - 1) / 2
• Each connection is a pair of distinct nodes (as a string "a b")
• No duplicate or self-loop connections are present