Codeforces Round 609 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

divide and conquer

graphs

math

*3200

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Invertation in Tournament

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a tournament — complete directed graph.

In one operation you can pick any vertex $$$v$$$ and change the direction of all edges with $$$v$$$ on one of the ends (i.e all edges $$$u \to v$$$ change their orientation to $$$v \to u$$$ and vice versa).

You want to make the tournament strongly connected with the smallest possible number of such operations if it is possible.

Also, if it is possible, you need to find the number of ways to make this number of operations to make graph strongly connected (two ways are different if for some $$$i$$$ vertex that we chose on $$$i$$$-th operation in one way is different from vertex that we chose on $$$i$$$-th operation in another way). You only need to find this value modulo $$$998\,244\,353$$$.

Input

The first line of input contains one integer $$$n$$$ ($$$3 \leq n \leq 2000$$$): the number of vertices in the tournament.

Following $$$n$$$ lines contain a description of the given tournament, each of them contains a binary string of length $$$n$$$. If $$$j$$$-th character of $$$i$$$-th string is equal to '1', then the graph has an edge $$$i \to j$$$.

It is guaranteed that there are no edges $$$i \to i$$$ and the graph has exactly one edge among $$$i \to j$$$ and $$$j \to i$$$ for different $$$i$$$ and $$$j$$$.

Output

If it is not possible to convert tournament to strongly connected with the given operations, output "-1".

Otherwise, output two integers: the smallest number of operations that you need to make the given graph strongly connected and the number of ways to do this number of operations to make graph strongly connected, modulo $$$998\,244\,353$$$.

Examples

Input

3 010 001 100

Output

0 1

Input

4 0010 1000 0100 1110

Output

-1

Input

6 010000 001000 100000 111001 111100 111010

Output

2 18

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/20/2024 11:02:03 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|