Satori wants to know if there is an undirected graph/a simple undirected graph/a tree whose sequence of degrees = array a.

Submit: 1503 Solved: 223

[Submit][Status][Web Board]

Given an array \(a_1,a_2,...,a_n\) which means the degree of nodes.

Satori wants to know if there is an undirected graph/a simple undirected graph/a tree whose sequence of degrees = array a.

The first line contains an integer \(n(1\le n\le100000)\), i.e. the number of nodes.

Then one line follows. It contains n integers \(a_i\le 10000000\), which means the degree of node i is \(a_i\).

Then one line follows. It contains n integers \(a_i\le 10000000\), which means the degree of node i is \(a_i\).

The first line print "YES"(without quotes) if there is an undirected graph whose sequence of degrees = array a, and "NO"(without quotes) otherwise.

The second line print"YES"(without quotes) if there is a simple undirected graph whose sequence of degrees = array a, and "NO"(without quotes) otherwise.

The third line print"YES"(without quotes) if there is a tree whose sequence of degrees = array a, and "NO"(without quotes) otherwise.

The second line print"YES"(without quotes) if there is a simple undirected graph whose sequence of degrees = array a, and "NO"(without quotes) otherwise.

The third line print"YES"(without quotes) if there is a tree whose sequence of degrees = array a, and "NO"(without quotes) otherwise.

```
6
3 3 1 1 1 1
```

```
YES
YES
YES
```