import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
public class Main {
private final RoomNode[] rooms;
private final int passages;
private long noOfPairsWhichHaveDraughts = 0;
private long noOfRoomsWithAtleastOneDraught = 0;
String[] roomAndPassage
= in.
readLine().
split(" "); int noOfRooms
= Integer.
parseInt(roomAndPassage
[0]); if (noOfRooms > 50000) {noOfRooms = 50000;}
passages
= Integer.
parseInt(roomAndPassage
[1]);
rooms = new RoomNode[noOfRooms];
setRoomsWithOpenWindows(in);
setPairsWithDraughts(in);
findSolution();
}
int i = 0;
String[] line
= in.
readLine().
trim().
split(" ");
for (String roomToken
: line
) { boolean openWindow
= Integer.
parseInt(roomToken
) == 1? true:false; rooms[i] = new RoomNode(openWindow);
i++;
if (i>=rooms.length) {break;}
}
}
int i = 0;
while((line = in.readLine()) != null && !line.isEmpty() & i <= passages) {
line = line.trim();
String[] lineTokens
= line.
split(" "); RoomNode room1
= rooms
[Integer.
parseInt(lineTokens
[0])-1]; RoomNode room2
= rooms
[Integer.
parseInt(lineTokens
[1])-1]; room1.addLinks(room2);
room2.setParent(room1);
i++;
}
}
private void findSolution() {
Deque<RoomNode> stack = new ArrayDeque<>();
int pruned = 0;
int openCount = 0;
for (RoomNode room: rooms) {
pruned += pruneTree(room);
if (room.isVisited() || !room.isOpenWindow()) {continue;}
stack.clear();
stack.push(room);
while(!stack.isEmpty()) {
RoomNode node = stack.pop();
node.setVisited(true);
if (node.isOpenWindow()) {openCount++;}
stack.addAll(node.getLinks());
}
}
if (openCount > 1) {
noOfPairsWhichHaveDraughts += ((openCount * (openCount-1))/2);
noOfRoomsWithAtleastOneDraught = rooms.length - pruned;
}
}
private int pruneTree(RoomNode room) {
Deque<RoomNode> stack = new ArrayDeque<>();
int pruned = 0;
if (room.isOpenWindow()) {return 0;}
stack.push(room);
while(!stack.isEmpty()) {
RoomNode node = stack.pop();
if (!node.isOpenWindow() && node.getLinks().isEmpty()) {
pruned++;
node.parent.getLinks().remove(node);
stack.push(node.getParent());
}
}
return pruned;
}
return noOfPairsWhichHaveDraughts + " " + noOfRoomsWithAtleastOneDraught;
}
public static void main
(String[] args
) { Main draughts;
draughts = new Main(in);
System.
out.
println(draughts.
getSolution()); e.printStackTrace();
}
}
private class RoomNode {
private final boolean openWindow;
private final ArrayList<RoomNode> links = new ArrayList<>();
private RoomNode parent;
private boolean visited;
public RoomNode (boolean openWindow) {
this.openWindow = openWindow;
visited = false;
setParent(null);
}
public boolean isOpenWindow() {
return openWindow;
}
public void addLinks(RoomNode link) {
links.add(link);
}
public ArrayList<RoomNode> getLinks() {
return links;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public RoomNode getParent() {
return parent;
}
public void setParent(RoomNode parent) {
this.parent = parent;
}
}
}