# Tag-tarjan

Icontofig 's Blog // 我们的征程是星辰大海！Away From OI，Come to ICPC（查看友链请点About Me）

## Description

You are given an undirected graph G = (V, E) containing N nodes and M edges. The nodes are numbered from 1 to N. A subset C of V is a vertex cover if for every edge (u, v) ∈ E, at least one of u and v belong to C. Note that C = V is always a vertex cover.
Consider a partition of V into two sets A and B. It is said to be a valid partition, if the following two conditions are satisfied: A should be a vertex cover. And for each i such that 1 ≤ i ≤ n/2, nodes 2i and 2i - 1 don't belong to the same set (i.e. one belongs to set A and the other to set B).
Determine if a valid partition exists. If it exists, provide an example of one valid partition.

## Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M denoting the number of nodes and number of edges in the graph respectively.
Each of the following M lines contains two space-se

## 题目描述

```3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0﻿​```

`25﻿​`

### 题解

#### 网络流建图方式：

score小于零的：从此点向汇点T连边，流量为-score

### 代码

```#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == '```
Title - Artist
0:00