I am reading a lot of tutorials that state two things.

1. "[Replacing fully connected layers with convolutional layers] casts them into fully convolutional networks that take input of any size and output classification maps." [Fully Convolutional Networks for Semantic Segmentation, Shelhamer et al.](https://people.eecs.berkeley.edu/~jonlong/long_shelhamer_fcn.pdf)
2. A traditional CNN can't do this because it has a fully connected layer and it's shape is decided by the input image size.

Based on these statements, my questions are the following?

1. Whenever I've made a FCN, I could only get it to work with a fixed dimension of input images for both training and testing. **But in the paper's abstract, they note: "Our key insight is to build “fully convolutional” networks that take input of arbitrary size and produce correspondingly-sized output with efficient inference and learning."** How is this possible the first layer has a fixed number of weights, and an input image of different sizes would not properly link to these weights.
2. How exactly does the input image size determine the fully connected layer? I tried looking online, but couldn't find a direct answer.